package com.jxb.three;

import java.util.Arrays;

/**
 * 重要！！！！！！
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 示例 1:
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * [1,2,3,4,5,6]
 * 输出: 5
 * 示例2:
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 */
public class KthInArray_215 {

    public static void main(String[] args) {

    }

    //使用jdk的排序
    //时:O(Nlog(n)),空:O(Nlog(n))
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    //使用快排的方式
    public int quick(int[] nums, int k) {
        //使用快排
        sort(nums,0,nums.length-1);
        //获取倒数第k个元素
        return nums[nums.length - k];
    }

    private static int[] sort(int[] nums, int start, int end) {
        //将数据分割成2部分，获取分区指示器
        int zoneIndex = partition(nums,start,end);
//        if (zoneIndex > start) {
//            sort(nums,start,zoneIndex-1);
//        }
        if (zoneIndex < end) {
            sort(nums,zoneIndex+1,end);
        }
        return nums;
    }

    public static int partition(int[] array, int start, int end) {
        if (start == end) {
            return start;
        }

        //选择基数
        int pivot = array[end];
        //设置分区指示器
        int zoneIndex = start - 1;
        for (int i = start;i<=end;i++) {
            //当前元素小于等于基准数
            if (array[i] <= pivot) {
                //将分区指示器累加
                zoneIndex++;
                //若当前元素在分区指示器元素的右边时，交换当前元素和分区指示器的元素
                if (i > zoneIndex) {
                    int temp = array[i];
                    array[i] = array[zoneIndex];
                    array[zoneIndex] = temp;
                }
            }
        }
        return zoneIndex;
    }


    //堆排序
    public int heapSort(int[] nums, int k) {
        //先进行堆排序
        sortArray(nums);
        //再获取倒数第k个元素
        return nums[nums.length - k];
    }

    //数组长度
    int len;

    public int[] sortArray(int[] nums) {
        if (nums.length <= 0){
            return nums;
        }
        len = nums.length;
        //构建成一个最大堆
        buildMaxHeap(nums);
        while (len > 0) {
            swap(nums,0,len - 1);
            len--;
            adjustHeap(nums,0);
        }
        return nums;
    }

    private void buildMaxHeap(int[] nums) {
        for (int i = (len/2 - 1);i>=0;i--) {
            adjustHeap(nums,i);
        }
    }

    private  void adjustHeap(int[] nums, int i) {
        int maxIndex = i;
        int left = 2*i + 1;
        int right = 2*(i+1);
        if (right < len && nums[right] > nums[maxIndex] && nums[right] > nums[left]) {
            maxIndex = right;
        }
        if (left < len && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        if (i != maxIndex) {
            swap(nums,maxIndex,i);
            adjustHeap(nums,maxIndex);
        }
    }


    private static void swap(int[] nums, int maxIndex, int i) {
        int temp = nums[maxIndex];
        nums[maxIndex] = nums[i];
        nums[i] = temp;
        System.out.println("经过一次调整的数组："+Arrays.toString(nums));
    }



}
